#!/usr/bin/env python3

def merge_sort(seq):
    num = len(seq)
    if num < 2:
        return list(seq)
    middle = int(num/2)
    left = merge_sort(seq[:middle])
    right = merge_sort(seq[middle:])
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0))
    return result


if __name__ == '__main__':
    seq = [72,6,57,88,60,42,83,73,48,85]
    print('Origin seq:', seq)
    seq = merge_sort(seq)
    print('Sorted seq:', seq)
    print('OK!' if seq == sorted(seq) else 'Wrong!!!')
